package algorithm.tree;

import algorithm.Node;

/**
 * 平衡树
 *
 * @author csp 2021-12-12
 */
public class Code04_CheckBlanceTree {

    /*
        每一子树。左右高度差<=1


     */

    public static class ReturnType {
        public boolean isBlanced;
        public int height;

        public ReturnType(boolean isBlanced, int height) {
            this.isBlanced = isBlanced;
            this.height = height;
        }
    }

    /**
     * 树
     * 树型DP
     *
     * @param x
     * @return
     */
    public static ReturnType process(Node x) {
        if (x == null) {
            return new ReturnType(true, 0);
        }
        ReturnType left = process(x.left);
        ReturnType right = process(x.right);
        int height = Math.max(left.height, right.height) + 1;
        boolean isBlanced = left.isBlanced && right.isBlanced && Math.abs(left.height - right.height) < 2;
        return new ReturnType(isBlanced, height);
    }



}
